package com.zdp.leetcodeMiddle;

import java.util.*;

/*
* 题目描述：
* 你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。
* 例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。
* 但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
示例 1：
输入： pattern = "abba", value = "dogcatcatdog"
输出： true
示例 2：
输入： pattern = "abba", value = "dogcatcatfish"
输出： false
示例 3：
输入： pattern = "aaaa", value = "dogcatcatdog"
输出： false
示例 4：
输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则
提示：
1 <= len(pattern) <= 1000
0 <= len(value) <= 1000
你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pattern-matching-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 模式匹配 {
    public static void main(String[] args) {
        模式匹配 demo = new 模式匹配();
        char[] a = new char[5];
        System.out.println(a[0]=='\0');
        System.out.println(demo.patternMatching1("abab",
                "dogcatdogcat"));
    }
    /*
     * 思路，通过确认a和b的长度 来进行匹配 ---> 因为只有两个字母，所以可以遍历他们所代表的串的长度，如果多一个字母就难了
     * 二元一次比三元一次好解
     * 首先计算出a和b的个数，要注意特殊情况，即模式串里只有a 和只有b的情况
     * Ca:a的个数 Cb:b的个数 lp:模式串长度  lv:匹配串长度  la:a的长度  lb:b的长度
     * 则我们可以得到式子 ： Ca*la+(lv-Ca)*lb = lv  ===> 即我们只需要遍历la的长度，就可以得到lb的长度
     * lb = ( lv - Cb )/ Ca
     * 当我们解得 lb 的长度后 ，就可以对串进行匹配
     * 我是创建两个数组 分别存放 a 和 b 的字符串
     * 遍历模式串，当第一次出现a时，填入a字符串，第一次出现b时，填入b字符串
     * 再次出现a或者b时， 进行匹配
     * （还有一个特殊情况，即a和b的个数都不为0时，匹配串为空，这边就要处理a==b=""的情况）
     * 若匹配成功，要注意a==b的情况，要进行判断
     * */
    public boolean patternMatching(String pattern, String value) {
        //先计算出a的个数
        int ca =0;
        for(int i=0;i<pattern.length();i++){
            if(pattern.charAt(i)=='a')
                ca++;
        }
        int cb = pattern.length()-ca;
        if(ca==0||cb==0){
            int n =ca==0?cb:ca;
            return judge(value,n,0);
        }
        boolean flag = false;
        //如果模式串不是只有一种字母 ,那就遍历a的长度，计算出b的长度
        label1:
        for(int i=0;i<=value.length()/ca;i++){
            if(flag)
                return true;
            double jj =((double)value.length()-ca*i)/cb;
            int j = (int)jj;
            if(jj==j){
                if(i==0||i==value.length()/ca){
                    int n =i==0?cb:ca;
                    flag = judge(value,n,1);
                    continue;
                }
                //找到了,就开始进行匹配
                //首先要保存a 和 b的字符串
                char[] a = new char[i];
                char[] b = new char[j];
                //遍历模式串
                int pos = 0;
                for(int l = 0;l<pattern.length();l++){
                    int abi = 0;
                    if(pattern.charAt(l)=='a'){
                        //如果a是第一次出现，那就获取到a的字符串
                        if(a[0]=='\0'){
                            for(int k=0;k<i;k++){
                                a[abi] = value.charAt(pos);
                                abi++;
                                pos++;
                            }
                        }else{
                            //如果不是第一次出现，就进行匹配
                            for(int k=0;k<i;k++){
                                if(a[abi]!=value.charAt(pos))
                                    continue label1;
                                abi++;
                                pos++;
                            }
                        }
                    }else{
                        if(b[0]=='\0'){
                            for(int k=0;k<j;k++){
                                b[abi] = value.charAt(pos);
                                abi++;
                                pos++;
                            }
                        }else{
                            for(int k=0;k<j;k++){
                                if(b[abi]!=value.charAt(pos))
                                    continue label1;
                                abi++;
                                pos++;
                            }
                        }
                    }
                }
                if(!Arrays.equals(a,b))
                flag = true;
            }
        }
        return flag;
    }

    public boolean judge(String value,int n,int temp){
        int length = value.length();
        if(length%n!=0){
            return false;
        }
        //划分，然后判断
         length = length/n;
        char[] a = new char[length];
        for(int i=0;i<length;i++){
            a[i] = value.charAt(i);
        }
        int j=0;
        for(int i=length;i<value.length();i++){
            if(value.charAt(i)!=a[j]){
                return false;
            }
            j = (j+1)%length;
        }
        if(temp!=0){
            if(a.length==0)
                return false;
        }
        return true;
    }

    /*
    * 还可以使用回溯法 即每次都只要判断模式串的头个字母 与 主串是否匹配
    * 如果不匹配，就回溯
    * */
    public boolean patternMatching1(String pattern, String value) {
        Map<Character,String> m = new HashMap<>();
        Set<String> s = new HashSet<>();
        return f(pattern,value,m,s);
    }
    public boolean f(String pattern, String value, Map<Character,String> m, Set<String> s){
        //先来个终结条件
        if(pattern.equals("")){
            //模式串已经遍历到头了
            return value.equals(""); //若匹配串也到头，说明匹配成功，否则匹配失败
        }
        //首先判断模式串中第一个字母 是否已经有匹配的字符串了
        String one = m.get(pattern.charAt(0));
        if(one!=null){
            //不等于就进行匹配
            if(value.startsWith(one)){ //如果匹配串的头字母匹配，那就进行下一个头字母的匹配
                return f(pattern.substring(1),value.substring(one.length()),m,s);
            }
            //不匹配就返回flase,进行回溯，选择a或b可能匹配的其他串
            return false;
        }else{
            //遍历所有的可能，因为有空串的可能性
            for(int i=-1;i<value.length();i++){
                String c = value.substring(0,i+1);
                if(s.contains(c)) //不能是同一个
                    continue;
                s.add(c);
                m.put(pattern.charAt(0),c);//存储一下a或b对应的串
                //然后继续匹配 ,若满足条件，就返回true,若不满足条件，就重新选择a或b 对应的字符串
                if(f(pattern.substring(1),value.substring(i+1),m,s)){
                    return true;
                }
                //将当前 对应的串删除
                m.remove(pattern.charAt(0));
                s.remove(c);
                //遍历其他串的可能性
            }
            //遍历完成 --->说明没有满足条件的
            return false;
        }

    }
}
